This invention relates to the technologies of digital data communication, digital pattern recognition, digital sorting and search processing, data compression processing and wire speed Internet network routing.
The Internet currently has a few tens of backbone routers, each serving up to a few thousand smaller enterprise networks. The major performance bottleneck in backbone routers is the time taken to look up a route in a forwarding table. On receiving a data packet, an input port looks up the packet""s destination address in its forwarding table to determine the packet""s destination port. Since the forwarding table may contain a large number of routing entries, it is time consuming to match an incoming packet with these routing entries. Furthermore, to reduce database size and routing update traffic, the forwarding table typically contains a smaller set of prefixes, instead of all of the assigned Internet addresses. This requires a more complex lookup because an incoming packet may match multiple routing entries and the entry with the longest prefix match needs to be determined.
Prefixes are patterns that match the first n binary bits of a destination address, where n is a positive integer. The forwarding table stores routing entries that are typically of the form  less than network address/mask, port greater than , where xe2x80x9cmaskxe2x80x9d is a number that specifies the first number of bits in the xe2x80x9cnetwork addressxe2x80x9d as the prefix to be matched for xe2x80x9cport,xe2x80x9d which identifies a specific destination port. The speed of a route lookup is determined by the number of memory access required to find the matching route entry, and by the speed of the memory. Data structures for the route entries in the forwarding table can be designed to reduce lookup time. A second consideration in designing forwarding table data structures is the time taken for table updates, such as prefix insertion, deletion, route change, and the like. Since a forwarding table may need to be updated relatively less frequently, conventional forwarding table data structures and address matching algorithms are usually designed to optimize route lookup at the expense of the time taken to update the table.
A common type of data structure for the forwarding table is a trie. The trie is a general-purpose data structure for storing strings, where each string is represented by a leaf in a tree structure and the value of the string corresponds to the path from the root of the tree to the leaf. A basic trie structure 101 for a set of binary strings (P1, P2, P3, P4, P5, P6, P7, and P8) is shown in FIG. 1A. This simple structure is not very efficient. The number of nodes (N1 to N13) may be large and the average depth (the average length of a path from the root to the longest matching prefix) may be long. As an improvement, Srinivasan and Varghese designed a data structure and searching algorithm called controlled prefix expansion. See V. Srinivasan and G. Varghese, xe2x80x9cFaster IP Lookups Using Controlled Prefix Expansion,xe2x80x9d ACM Sigmetrics""98, ACM Transactions on Computer Systems, March 1999. The data structure and search algorithm is based on a well-known fact that a smaller number of distinct prefix lengths lead to faster search for the longest prefix match. Using the controlled prefix expansion, a set of prefixes with M distinct lengths is converted to a set of prefixes with N distinct lengths, where N less than M. FIG. 1B illustrates how the original set of prefixes in FIG. 1A, which has 7 distinct lengths, can be expanded into an expanded set of prefixes having 3 distinct lengths. FIG. 1B also shows how the expanded prefix set is placed in a multi-bit trie having a maximum path length of 3 compared to the binary trie in FIG. 1A that has a maximum path length of 7.
However, the controlled expansion search algorithm has the disadvantage of requiring prefix expansion for prefix lengths that are different from the N distinct lengths. Prefix expansion typically requires complicated software processing such as prefix sorting, prefix expanding, prefix restructuring, and the like when the lookup table is being updated. When prefix number reaches multi-million or more in a backbone router, the computer power consumed to handle these processing tasks will be significant. Furthermore, the controlled expansion search algorithm typically requires a special mechanism to handle multiple destinations on a same trie-walking path of multi-bit tries. One example of such a special mechanism is an auxiliary table for multiple destinations, which usually increases lookup latency and slows down performance of a lookup engine.
The present invention provides a method of searching for a longest prefix match for an address having a number of binary bits among a plurality of entries having different lengths of bits. The entries are associated with a trie having a first number of trie nodes for L-bit trie match, wherein L is a predetermined integer greater than 1, and at least a first trie unit including at least one trie node for K1-bit trie match and at least one trie node for K2-bit trie match, wherein K1 and K2 are two different positive integers. Each of the entries corresponds to one trie node, and at least one trie node for L-bit trie match points to the first trie unit. Each trie node corresponds to a first, second, third, or fourth type of trie node. The method of searching according to an embodiment of the present invention first splits the address into at least a first key and a second key, each key including a predetermined number of address bits. Then, it determines a first matching node among the first number of trie nodes based on the address bits in the first key. Responsive to the first matching node corresponding to the first or second trie node type, the method selects the entry corresponding to the first matching node as the longest prefix match for the address. Also, responsive to the first matching node corresponding to the third or fourth trie node type, the method determines at least one second matching node in the first trie unit based upon the address bits in the second key.
According to another embodiment of the present invention, the trie further includes at least a second trie unit and the address is further split into at least a third key. The method of searching further determines the trie node type of the second matching node. Responsive to the second matching node corresponding to the first or second trie node type, the method selects the entry corresponding to the second matching node as the longest prefix match for the address. Responsive to the second matching node corresponding to the third or fourth trie node type, the method determines a third matching node in the second trie unit based upon the address bits in the third key.
According to one embodiment of the present invention, the address is an Internet address included in an Internet data packet and the entries include prefixes each associated with a destination port in an Internet router. The present invention enables fast and accurate routing of Internet data packets by using the trie structure according to the present invention.
According to still another embodiment of the present invention, a system searches for a longest prefix match for an address having a number of binary bits among a plurality of entries having different lengths of bits. The entries are associated with a trie having a first number of trie nodes for L-bit trie match, wherein L is a predetermined integer greater than 1, and at least a first trie unit including at least one trie node for K1-bit trie match and at least one trie node for K2-bit trie match, wherein K1 and K2 are two different positive integers. Each of the plurality of entries corresponding to one trie node, and at least one trie node for L-bit trie match points to a trie unit. Each trie node corresponds to a first, second, third, or fourth type of trie node. The system comprises at least a first memory unit and a second memory unit coupled to the first memory unit, the first memory unit storing the first number of trie nodes and the second memory unit storing the first trie unit. The system also comprises at least a match decoder coupled to the second memory subunit and configured to match respective bits of the address with respective trie nodes in the trie unit stored in the second memory unit.
The hybrid trie structure of the present invention enables fast and accurate routing of Internet data packets, because the look-up process is shortened to merely L levels (stages) by the use of hybrid trie units, i.e., the critical path is significantly shortened. In addition, the look-up process is not complicated so as to require complicated software and does not present a computational burden on the processors in Internet routers. Thus, the address lookup engine of the present invention is suitable for very high-speed Internet network routing. The design of the hybrid trie is not complicated and is very highly pipelined, thus being suitable for high-density integrated circuit design. In addition, Internet routers embodying the hybrid trie structure of the present invention would consume only a small amount of power because the lookup process does not require complicated software processing compared with traditional longest match trie approaches.
According to still another embodiment of the present invention, a method inserts an entry having a destination pointer into a trie node in a trie used for a longest prefix match of an address having a number of binary bits. The trie has a first number of trie nodes for L-bit trie match, wherein L is a predetermined integer greater than 1, and at least a first trie unit including at least one trie node for K1-bit trie match and at least one trie node for K2-bit trie match, wherein K1 and K2 are two different positive integers and K1 is smaller than K2. At least one trie node for L-bit trie match points to the first trie unit, and each trie node is one of a free node, a leaf node, a path node, and a path-leaf node, the method comprising. The method first receives an insertion address, and splits the insertion address into at least a first key and a second key, each key including a predetermined number of address bits. The method determines a first matching node among the first number of trie nodes based on the address bits in the first key, the first matching node being the matching node for the L-bit trie match. Then, the method determines the node type of the first matching node. Responsive to the first matching node being a free node, the method changes the first matching node to a leaf node and assigns the destination pointer to the first matching node. Responsive to the first matching node being a leaf node, the method assigns the destination pointer to the first matching node. Responsive to the first matching node being a path node, the method changes the first matching node to a path-leaf node and conducts stack processing to update free nodes downstream the first matching node with the destination pointer. Responsive to the first matching node being a path-leaf node, the method conducts stack processing to update free nodes downstream the first matching node with the destination pointer.
According to still another embodiment of the present invention, a method deletes an entry from a trie node in a trie used for a longest prefix match of an address having a number of binary bits. The trie has a first number of trie nodes for L-bit trie match, wherein L is a predetermined integer greater than 1, and at least a first trie unit including at least one trie node for K1-bit trie match and at least one trie node for K2-bit trie match, wherein K1 and K2 are two different positive integers and K1 is smaller than K2. At least one trie node for L-bit trie match points to the first trie unit, and each trie node is one of a free node, a leaf node, a path node, and a path-leaf node. The method first receiving a deletion address, and splits the deletion address into at least a first key and a second key, each key including a predetermined number of address bits. Then, the method determines a first matching node among the first number of trie nodes based on the address bits in the first key, the first matching node being the matching node for the L-bit trie match. The method determines the node type of the first matching node. Responsive to the first matching node being a leaf node, the method changes the first matching node to a free node and assigns a free pointer to the first matching node. Responsive to the first matching node being a path-leaf node, the method changes the first matching node to a path node and conducts stack processing to update free nodes downstream the first matching node with the free pointer.